package Tree_09.HuffmanTree_05;

/*
 * @Author 罗
 * @date 2020/3/22 - 10:42 下午
 *
 */


import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class HuffmanTree {
    /**
     * 基本介绍
     * <p>
     * 给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree), 还有的书翻译为霍夫曼树。
     * 赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
     * <p>
     * (1)路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。
     * 通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1
     * (2)结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。
     * 结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积
     * (3)树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL(weighted path length) ,权值越大的结点离根结点越近的二叉树才是最优二叉树。
     * (4)WPL最小的就是赫夫曼树
     * 构成赫夫曼树的步骤：
     * 从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树
     * 取出根节点权值最小的两颗二叉树
     * 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
     * 再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复  1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树
     *
     * @param array
     * @return
     */
    public static Node createHuffmanTree(int[] array) {
        /*
         * 为了操作方便
         * 1.遍历array数组
         * 2.将array的每一个元素构成一个Node对象
         * 3.将Node对象放入到ArrayList中
         * */
        List<Node> nodeList = new LinkedList<>();
        for (int i = 0; i < array.length; i++) {
            nodeList.add(new Node(array[i]));
        }
        /*
         * 一直循环，直到只有一个节点为止
         *  得到的节点就是HuffmanTree的根节点
         *      取出两个最小的节点拼接然后再放回List，再排序
         *          这样循环操作，可以使得每次取出的两个节点都是最小的，这个节点可以是多个子节点的根节点
         *          这个小树根节点的权值=本树所有叶子节点的权值的和
         *      如果两个最小节点合并成parentNode之后，产生两个新的最小节点权值各自都比刚合成的parentNode的权值小
         *      则刚合成的parentNode会等到下一轮，本轮暂停。两个新的最小节点权值会被合成一个新的parentNode并被放入到List中
         *      这样就保证了Huffman树的有序
         * */
        while (nodeList.size() > 1) {
            /*
             * 4.因为Node类实现了Comparable接口，因此可以调用Collections来排序
             *   从小到大排序
             * */
            Collections.sort(nodeList);
            /*
             * 5.取出节点权值最小的两棵二叉树，这两棵二叉树没有子节点，但依然是二叉树
             * */
            Node leftNode = nodeList.get(0);
            Node rightNode = nodeList.get(1);
            /*
             * 6.为两个子节点构建一个父节点
             *   父节点的权值是两个子节点权值的和
             * */
            Node parentNode = new Node(leftNode.value + rightNode.value);
            /*
             * 7.并把父节点的left、right指针指向两个子节点
             * */
            parentNode.left = leftNode;
            parentNode.right = rightNode;
            /*
             * 8.从ArrayList中删除处理过的二叉树
             *      每删除一个节点，都会往前移动
             * */
//            nodeList.remove(0);
//            nodeList.remove(0);
            //第二种移除方法
            nodeList.remove(leftNode);
            nodeList.remove(rightNode);
            /*
             * 9.将parentNode加入到ArrayList中
             *
             * */
            nodeList.add(0, parentNode);
        }
        return nodeList.get(0);
    }

    /**
     * 普通前序遍历，用来遍历Huffman树
     */
    public static void preOrderList(Node node, int count) {
        if (node == null) {
            return;
        }
        count++;
        for (int i = 0; i < count; i++) {
            System.out.print("--");
        }
        System.out.println(node.value);
        if (node.left != null) {
            preOrderList(node.left, count);
        }
        if (node.right != null) {
            preOrderList(node.right, count);
        }
    }
}
